//题目:
// 在二维网格 grid 上，有 4 种类型的方格：
// 1 表示起始方格。且只有一个起始方格。
// 2 表示结束方格，且只有一个结束方格。
// 0 表示我们可以走过的空方格。
// -1 表示我们无法跨越的障碍。
// 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
// 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码:
class Solution 
{
    int ret=0;
    bool flag[20][20]={false};
    int arr_x[4]={-1,1,0,0},arr_y[4]={0,0,-1,1};
public:
    bool is_space_left(vector<vector<int>>& grid)
    {
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j]==0)
                    return true;
            }
        }
        return false;
    }
    void dfs(vector<vector<int>>& grid,int row,int col)
    {
        if(grid[row][col]==2){
            //判断grid中是否剩有空白格
            if(is_space_left(grid)==false)ret++;
            return;
        }
        //进入grid中(row,col)的相邻位置
        for(int i=0;i<4;i++)
        {
            int x=row+arr_x[i],y=col+arr_y[i];
            if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size() && flag[x][y]==false && (grid[x][y]==0 || grid[x][y]==2))
            {
                flag[x][y]==true;
                if(grid[x][y] != 2)grid[x][y] = -1;
                dfs(grid,x,y);
                //回溯
                flag[x][y]==false;
                if(grid[x][y] != 2)grid[x][y] = 0;
            }
        }
    }
    int uniquePathsIII(vector<vector<int>>& grid) 
    {   
        //1.在grid中找到值为1的位置
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j]==1)
                    dfs(grid,i,j);
            }
        }

        return ret;
    }
};